package DataStructure;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28792
 * Date: 2025-11-10
 * Time: 10:43
 */
public class MyList implements IList {

    private static class Node {
        public int data;
        public Node next;
        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node first;
    private Node last;
    private int size;

    public MyList() {
    }

    private void checkIndex(int index) {
        if (index < 0 || index > size) {
            throw new RuntimeException("index不合法");
        }
    }

    @Override
    public void addFirst(int data) {
        Node node = new Node(data, first);
        if (first == null) {
            last = node;
        }
        first = node;
        size++;
    }

    @Override
    public void addLast(int data) {
        Node node = new Node(data, null);
        if (first == null) {
            first = node;
            last = node;
        } else {
            last.next = node;
        }
        size++;
    }

    @Override
    public void addIndex(int index, int data) {
        checkIndex(index);
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size) {
            addLast(data);
            return;
        }
        Node prevNode = first;
        while(index-- > 1) {
            prevNode = prevNode.next;
        }
        Node nextNode = prevNode.next;
        prevNode.next = new Node(data, nextNode);
        size++;
    }

    @Override
    public boolean contains(int key) {
        Node cur = first;
        while (cur != null) {
            if (cur.data == key)
                return true;
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        Node cur = first;
        if (cur == null) {
            throw new RuntimeException("链表为空");
        }
        if (cur.data == key) {
            first = first.next;
            return;
        }
        while (cur.next != null) {
            Node nextNode = cur.next;
            if (nextNode.data == key) {
                cur.next = nextNode.next;
                nextNode.next = null;
                last = (nextNode == last) ? cur : last;
                return;
            }
            cur = nextNode;
        }
        throw new RuntimeException("key不存在");
    }


    @Override
    public void removeAllKey(int key) {
        Node cur = first;
        if (cur == null) {
            throw new RuntimeException("链表为空");
        }
        while (cur.next != null) {
            Node nextNode = cur.next;
            if (nextNode.data == key) {
                cur.next = nextNode.next;
                nextNode.next = null;
            } else {
                cur = nextNode;
            }
        }
        if (first.data == key) {
            Node nextNode = first.next;
            first.next = null;
            first = nextNode;
        }
        if (first == null) {
            last = null;
        } else {
            last = cur;
        }
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public void clear() {
        Node cur = first;
        while (cur != null) {
            Node nextNode = cur.next;
            cur.next = null;
            cur = nextNode;
        }
        first = last = null;
    }

    @Override
    public void display() {
        Node cur = first;
        while (cur != null) {
            System.out.println(cur.data);
            cur = cur.next;
        }

    }
}
